package cn.blunce.SomeTips;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by Experiment on 2016/4/5 0005.
 *
 * There are 3 ways to do the Fibonacci.
 */
public class Fibonacci {
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    public int getFibonacci(int n) {
        if (n == 0 || n == 1)
            return 1;
        return getFibonacci(n - 1) + getFibonacci(n - 2);
    }

    public int getFibonacci1(int n) {
        if (map.containsKey(n))
            return map.get(n);
        if (n == 0 || n == 1) {
            map.put(n, 1);
            return 1;
        }
        int tmp = getFibonacci1(n - 1) + getFibonacci1(n - 2);
        map.put(n, tmp);
        return tmp;
    }

    public int getFibonacci2(int n) {
        double tmp = Math.sqrt(5);
        double a = 1.0 / tmp;
        double b = (1.0 + tmp) / 2;
        return (int) Math.round(a * Math.pow(b, n + 1));
    }
}
